package com.jcy_lyh.searchingsorting;

import java.util.Arrays;
public class Sorting {
    //选择排序
    public String selectionSort(int[] data)
    {
        int min;
        int temp;

        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++)
                if (data[scan]<(data[min]))
                    min = scan;

            swap(data, min, index);
        }
        return  Arrays.toString(data);
    }

    private  void swap(int[] data, int index1, int index2)
    {
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
    //冒泡排序
    public String bubbleSort(int[] numbers)
    {
        int temp = 0;
        int size = numbers.length;
        for(int i = 0 ; i < size-1; i ++)
        {
            for(int j = 0 ;j < size-1-i ; j++)
            {
                if(numbers[j] > numbers[j+1])  //交换两数位置
                {
                    temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
                }
            }
        }
        return Arrays.toString(numbers);
    }
    //插入排序
    public String insertionSort(int[] data)
    {
        for (int index = 1; index < data.length; index++)
        {
            int key = data[index];
            int position = index;

            // shift larger values to the right
            while (position > 0 && data[position-1]>key)
            {
                data[position] = data[position-1];//把数值大的数换到了右边
                position--;//position变成左边数的索引
            }

            data[position] = key;
        }
        return Arrays.toString(data);
    }

    /*希尔排序
    希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
    随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
     */

    public String ShellSort(int[] data)
    {
        int m = 0;
        int temp = 0;
        //  每次将步长缩短为原来的一半
        for (int gap = data.length / 2; gap > 0; gap =gap/2)
        {
            for (int i = gap; i < data.length; i++)
            {   //temp保存索引为初始gap的值
                temp = data[i];
                //从i开始，
                for (m = i; m >= gap; m = m-gap)
                {  //将按步长分好的同组元素进行比较
                    if(temp < data[m - gap])
                    {//升序
                        data[m] = data[m - gap];
                    }
                    else
                    {
                        break;
                    }
                }
                data[m] = temp;
            }
        }
        return Arrays.toString(data);
    }
    //堆排序
    public String HeapSort(int[] data)
    {
        ArrayHeap temp = new ArrayHeap();

        // copy the array into a heap
        for (int i = 0; i < data.length; i++)
            temp.addElement(data[i]);

        // place the sorted elements back into the array
        int count = 0;
        while (!(temp.isEmpty()))
        {
            data[count] = (int) temp.removeMin();
            count++;
        }
        return Arrays.toString(data);
    }
    /**
     * 归并排序
     * 将两个（或两个以上）有序表合并成一个新的有序表
     * 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
     */
    public void mergeSort(int[] data)
    {
        mergeSort(data, 0, data.length - 1);
    }


    private  void mergeSort(int[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid+1, max);
            merge(data, min, mid, max);
        }
    }
    @SuppressWarnings("unchecked")
    private void merge(int[] data, int first, int mid, int last)
    {
        int[] temp = new int[data.length];

        int first1 = first, last1 = mid;  // endpoints of first subarray第一个子数组的端点
        int first2 = mid+1, last2 = last;  // endpoints of second subarray第二个子数组的端点
        int index = first1;  // next index open in temp array

        //  Copy smaller item from each subarray into temp until one
        //  of the subarrays is exhausted
        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1]<data[first2])
            {
                temp[index] = data[first1];
                first1++;
            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }

        //  Copy remaining elements from first subarray, if any
        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
        }

        //  Copy remaining elements from second subarray, if any
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }

        //  Copy merged data into original array
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }

    //快速排序法
    public void quickSort(int[] data)
    {
        quickSort(data, 0, data.length - 1);
    }

    private void quickSort(int[] data, int min, int max)
    {
        if (min < max)
        {
            // create partitions
            int indexofpartition = partition(data, min, max);

            // sort the left partition (lower values)
            quickSort(data, min, indexofpartition - 1);

            // sort the right partition (higher values)
            quickSort(data, indexofpartition + 1, max);
        }
    }

    private  int partition(int[] data, int min, int max)
    {
        int partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        // use the middle data value as the partition element
        partitionelement = data[middle];
        // move it out of the way for now
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // search for an element that is > the partition element
            while (left < right && data[left] <= partitionelement)
                left++;

            // search for an element that is < the partition element
            while (data[right] > partitionelement)
                right--;

            // swap the elements
            if (left < right)
                swap(data, left, right);
        }

        // move the partition element into place
        swap(data, min, right);

        return right;
    }
}
